package week9.jsjf;

import weeek3.jsjf.LinkedQueue;
import weeek3.jsjf.QueueADT;
import week2.LinkedStack;
import week2.StackADT;
import week4.jsjf.ArrayUnorderedList;
import week4.jsjf.UnorderedListADT;

import java.text.NumberFormat;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class AirControl {
     public class AviationSystemGraph<T> {
        protected final int DEFAULT_CAPACITY = 5;
        protected int numVertices;
        protected Double[][] adjMatrix;
        protected T[] vertices;
        protected int modCount;

        public AviationSystemGraph() {
            numVertices = 0;
            this.adjMatrix = new Double[DEFAULT_CAPACITY][DEFAULT_CAPACITY];
            this.vertices = (T[])(new Object[DEFAULT_CAPACITY]);
        }

        public void addEdge(T vertex1, T vertex2, double weight) {
            addEdge(getIndex(vertex1),getIndex(vertex2),weight);
        }

        public void addEdge(int index1, int index2, double weight) {
            if (indexIsValid(index1) && indexIsValid(index2))
            {
                adjMatrix[index1][index2] = weight;
                adjMatrix[index2][index1] = weight;
                modCount++;
            }
        }

        public void removeEdge(T vertex1, T vertex2) {
            removeEdge(getIndex(vertex1),getIndex(vertex2));
        }
        public void removeEdge(int index1, int index2) {
            if (indexIsValid(index1) && indexIsValid(index2))
            {
                adjMatrix[index1][index2] =Double.POSITIVE_INFINITY;
                adjMatrix[index2][index1] = Double.POSITIVE_INFINITY;
                modCount++;
            }
        }

        public void addVertex(T vertex) {
            if ((numVertices + 1) == adjMatrix.length)
                expandCapacity();

            vertices[numVertices] = vertex;
            for (int i = 0; i <=numVertices; i++)
            {
                adjMatrix[numVertices][i] = Double.POSITIVE_INFINITY;
                adjMatrix[i][numVertices] = Double.POSITIVE_INFINITY;
            }
            numVertices++;
            modCount++;
        }
        public void removeVertex(T vertex) {
            removeVertex(getIndex(vertex));
        }
        public void removeVertex(int index)
        {
            if (indexIsValid(index))
            {
                for (int j = index;j<numVertices-1;j++)
                {
                    vertices[j] = vertices[j+1];
                }
                vertices[numVertices-1] = null;


                for (int i = index; i < numVertices-1; i++)
                {
                    for (int x=0;x<numVertices;x++)
                        adjMatrix[i][x] = adjMatrix[i+1][x];

                }

                for (int i = index; i < numVertices; i++)
                {
                    for (int x=0;x<numVertices;x++)
                        adjMatrix[x][i] = adjMatrix[x][i+1];
                }

                for (int i = 0; i < numVertices; i++)
                {
                    adjMatrix[numVertices][i] = Double.POSITIVE_INFINITY;
                    adjMatrix[i][numVertices] = Double.POSITIVE_INFINITY;
                }
                numVertices--;
                modCount++;
            }
        }

        public Iterator iteratorBFS(T startVertex) {
            return iteratorBFS(getIndex(startVertex));
        }
        public Iterator<T> iteratorBFS(int startIndex)
        {
            Integer x;
            QueueADT<Integer> traversalQueue = new LinkedQueue<Integer>();
            UnorderedListADT<T> resultList = new ArrayUnorderedList<T>();

            if (!indexIsValid(startIndex))
                return resultList.iterator();

            boolean[] visited = new boolean[numVertices];
            for (int i = 0; i < numVertices; i++)
                visited[i] = false;

            traversalQueue.enqueue(startIndex);
            visited[startIndex] = true;

            while (!traversalQueue.isEmpty())
            {
                x = traversalQueue.dequeue();
                resultList.addToRear(vertices[x]);

                //Find all vertices adjacent to x that have not been visited
                //     and queue them up

                for (int i = 0; i < numVertices; i++)
                {
                    if (adjMatrix[x][i]<Double.POSITIVE_INFINITY && !visited[i])
                    {
                        traversalQueue.enqueue(i);
                        visited[i] = true;
                    }
                }
            }
            return new NetworkIterator(resultList.iterator());
        }

        public Iterator iteratorDFS(T startVertex) {
            return iteratorDFS(getIndex(startVertex));
        }
        public Iterator<T> iteratorDFS(int startIndex)
        {
            Integer x;
            boolean found;
            StackADT<Integer> traversalStack = new LinkedStack<Integer>();
            UnorderedListADT<T> resultList = new ArrayUnorderedList<T>();
            boolean[] visited = new boolean[numVertices];

            if (!indexIsValid(startIndex))
                return resultList.iterator();

            for (int i = 0; i < numVertices; i++)
                visited[i] = false;

            traversalStack.push(startIndex);
            resultList.addToRear(vertices[startIndex]);
            visited[startIndex] = true;

            while (!traversalStack.isEmpty())
            {
                x = traversalStack.peek();
                found = false;

                //Find a vertex adjacent to x that has not been visited
                //     and push it on the stack
                for (int i = 0; (i < numVertices) && !found; i++)
                {
                    if (adjMatrix[x][i]<Double.POSITIVE_INFINITY && !visited[i])
                    {
                        traversalStack.push(i);
                        resultList.addToRear(vertices[i]);
                        visited[i] = true;
                        found = true;
                    }
                }
                if (!found && !traversalStack.isEmpty())
                    traversalStack.pop();
            }
            return new NetworkIterator(resultList.iterator());
        }

        public int shortestPathLength(T startVertex, T targetVertex)
        {
            return shortestPathLength(getIndex(startVertex), getIndex(targetVertex));
        }

        public int shortestPathLength(int startIndex, int targetIndex)
        {
            int result = 0;
            if (!indexIsValid(startIndex) || !indexIsValid(targetIndex))
                return 0;

            int index1;
            Iterator<Integer> it = iteratorShortestPathIndices(startIndex,
                    targetIndex);

            if (it.hasNext())
                index1 = ((Integer)it.next()).intValue();
            else
                return 0;

            while (it.hasNext())
            {
                result++;
                it.next();
            }

            return result;
        }
        public Iterator iteratorShortestPath(T startVertex, T targetVertex) {
            return iteratorShortestPath(getIndex(startVertex), getIndex(targetVertex));
        }
        public Iterator<T> iteratorShortestPath(int startIndex, int targetIndex)
        {
            UnorderedListADT<T> resultList = new ArrayUnorderedList<T>();
            if (!indexIsValid(startIndex) || !indexIsValid(targetIndex))
                return resultList.iterator();

            Iterator<Integer> it = iteratorShortestPathIndices(startIndex,
                    targetIndex);
            while (it.hasNext())
                resultList.addToRear(vertices[((Integer)it.next()).intValue()]);
            return new NetworkIterator(resultList.iterator());
        }
        protected Iterator<Integer> iteratorShortestPathIndices(int startIndex, int targetIndex)
        {
            int index = startIndex;
            int[] pathLength = new int[numVertices];
            int[] predecessor = new int[numVertices];
            QueueADT<Integer> traversalQueue = new LinkedQueue<Integer>();
            UnorderedListADT<Integer> resultList =
                    new ArrayUnorderedList<Integer>();

            if (!indexIsValid(startIndex) || !indexIsValid(targetIndex) ||
                    (startIndex == targetIndex))
                return resultList.iterator();

            boolean[] visited = new boolean[numVertices];
            for (int i = 0; i < numVertices; i++)
                visited[i] = false;

            traversalQueue.enqueue(Integer.valueOf(startIndex));
            visited[startIndex] = true;
            pathLength[startIndex] = 0;
            predecessor[startIndex] = -1;

            while (!traversalQueue.isEmpty() && (index != targetIndex))
            {
                index = (traversalQueue.dequeue()).intValue();

                //Update the pathLength for each unvisited vertex adjacent
                //     to the vertex at the current index.
                for (int i = 0; i < numVertices; i++)
                {
                    if (adjMatrix[index][i]<Double.POSITIVE_INFINITY && !visited[i])
                    {
                        pathLength[i] = pathLength[index] + 1;
                        predecessor[i] = index;
                        traversalQueue.enqueue(Integer.valueOf(i));
                        visited[i] = true;
                    }
                }

            }
            if (index != targetIndex)  // no path must have been found
                return resultList.iterator();

            StackADT<Integer> stack = new LinkedStack<Integer>();
            index = targetIndex;
            stack.push(Integer.valueOf(index));
            do
            {
                index = predecessor[index];
                stack.push(Integer.valueOf(index));
            } while (index != startIndex);

            while (!stack.isEmpty())
                resultList.addToRear(((Integer)stack.pop()));

            return new NetworkIndexIterator(resultList.iterator());
        }
        private double dijkstra(int index1,int index2) {
            int[] previous = new int[numVertices];
            Double[] distance = new Double[numVertices];
            boolean[] flag = new boolean[numVertices];

            for (int i = 0; i < numVertices; i++) {
                flag[i] = false;
                previous[i] = 0;
                distance[i] = adjMatrix[index1][i];
            }

            flag[index1] = true;
            distance[index1] = 0.0;

            int k = 0;
            StackADT<Integer> stack = new LinkedStack<Integer>();
            for (int i = 1; i < numVertices; i++) {
                Double min = Double.POSITIVE_INFINITY;
                for (int j = 0; j < numVertices; j++) {
                    if (flag[j]==false && distance[j]<min) {
                        min = distance[j];
                        k = j;
                    }
                }
                flag[k] = true;

                for (int j = 0; j < numVertices; j++) {
                    double temp = (adjMatrix[k][j]==Double.POSITIVE_INFINITY ?Double.POSITIVE_INFINITY : (min + adjMatrix[k][j]));
                    if (flag[j]==false && (temp<distance[j]) ) {
                        distance[j] = temp;
                        previous[j] = k;
                    }
                }

            }
            int index = index2;
            stack.push(index);
            do
            {
                index = previous[index];
                stack.push(index);
            }
            while (index != index1);
            if(distance[index2]<Double.POSITIVE_INFINITY)
            {
                String result = "";
                while (!stack.isEmpty())
                    result+=vertices[stack.pop()]+"-";
                System.out.println("最便宜的路径为："+result.subSequence(0,result.length()-1));
            }
            return distance[index2];
        }

        public boolean isEmpty() {
            return numVertices==0;
        }

        public boolean isConnected() {
            boolean result = true;
            for(int i=0;i<numVertices;i++){
                int temp=0;
                temp=getSizeOfIterator(this.iteratorBFS(vertices[i]));
                if(temp!=numVertices)
                {
                    result = false;
                    break;
                }
            }
            return result;
        }

        public int getSizeOfIterator(Iterator iterator) {
            int size = 0;
            while(iterator.hasNext()){
                size++;
                iterator.next();
            }
            return size;
        }

        public int size() {
            return numVertices;
        }

        protected boolean indexIsValid(int index)
        {
            if (index<size())
                return true;
            else
                return false;
        }

        public int getIndex(T vertex)
        {

            int index = numVertices-1;

            for (int i = 0; i < numVertices; i++) {
                if (vertex.equals(vertices[i])) {
                    index = i;
                    break;
                }
            }
            return index;
        }

        protected void expandCapacity()
        {
            T[] largerVertices = (T[])(new Object[vertices.length*2]);
            Double[][] largerAdjMatrix =
                    new Double[vertices.length*2][vertices.length*2];

            for (int i = 0; i < numVertices; i++)
            {
                for (int j = 0; j < numVertices; j++)
                {
                    largerAdjMatrix[i][j] = adjMatrix[i][j];
                }
                largerVertices[i] = vertices[i];
            }

            vertices = largerVertices;
            adjMatrix = largerAdjMatrix;
        }
        public String getShorPath(T index1,T index2)
        {
            String result = "";
            if (shortestPathLength(getIndex(index1),getIndex(index2))==0)
                return "无法连通城市:" + index1 + " - " + index2;
            else {
                String res = "";
                NumberFormat numberFormat = NumberFormat.getCurrencyInstance();

                result += "最便宜的价格为："+numberFormat.format(dijkstra(getIndex(index1),getIndex(index2))) + "\n";

                if(shortestPathLength(getIndex(index1),getIndex(index2)) == 1)
                    result += index1+"-"+index2 + "： 可以直达";
                else{
                    Iterator iterator = iteratorShortestPath(getIndex(index1),getIndex(index2));
                    while (iterator.hasNext())
                        res += iterator.next()+"-》";
                    result += index1+"-"+index2 + "： 不可直达  \n最短路径为："+res.subSequence(0,res.length() - 2);
                }
                return result;
            }
        }

        protected class NetworkIterator implements Iterator<T>
        {
            private int expectedModCount;
            private Iterator<T> iter;

            /**
             * Sets up this iterator using the specified iterator.
             *
             * @param iter the list iterator created by a graph traversal
             */
            public NetworkIterator(Iterator<T> iter)
            {
                this.iter = iter;
                expectedModCount = modCount;
            }

            /**
             * Returns true if this iterator has at least one more element
             * to deliver in the iteration.
             *
             * @return  true if this iterator has at least one more element to deliver
             *          in the iteration
             * @throws ConcurrentModificationException if the collection has changed
             *          while the iterator is in use
             */
            public boolean hasNext() throws ConcurrentModificationException
            {
                if (!(modCount == expectedModCount))
                    throw new ConcurrentModificationException();

                return (iter.hasNext());
            }

            /**
             * Returns the next element in the iteration. If there are no
             * more elements in this iteration, a NoSuchElementException is
             * thrown.
             *
             * @return the next element in the iteration
             * @throws NoSuchElementException if the iterator is empty
             */
            public T next() throws NoSuchElementException
            {
                if (hasNext())
                    return (iter.next());
                else
                    throw new NoSuchElementException();
            }

            /**
             * The remove operation is not supported.
             *
             * @throws UnsupportedOperationException if the remove operation is called
             */
            @Override
            public void remove()
            {
                throw new UnsupportedOperationException();
            }
        }

        /**
         * Inner class to represent an iterator over the indexes of this graph
         */
        protected class NetworkIndexIterator implements Iterator<Integer>
        {
            private int expectedModCount;
            private Iterator<Integer> iter;

            /**
             * Sets up this iterator using the specified iterator.
             *
             * @param iter the list iterator created by a graph traversal
             */
            public NetworkIndexIterator(Iterator<Integer> iter)
            {
                this.iter = iter;
                expectedModCount = modCount;
            }

            /**
             * Returns true if this iterator has at least one more element
             * to deliver in the iteration.
             *
             * @return  true if this iterator has at least one more element to deliver
             *          in the iteration
             * @throws  ConcurrentModificationException if the collection has changed
             *          while the iterator is in use
             */
            public boolean hasNext() throws ConcurrentModificationException
            {
                if (!(modCount == expectedModCount))
                    throw new ConcurrentModificationException();

                return (iter.hasNext());
            }

            /**
             * Returns the next element in the iteration. If there are no
             * more elements in this iteration, a NoSuchElementException is
             * thrown.
             *
             * @return the next element in the iteration
             * @throws NoSuchElementException if the iterator is empty
             */
            public Integer next() throws NoSuchElementException
            {
                if (hasNext())
                    return (iter.next());
                else
                    throw new NoSuchElementException();
            }

            /**
             * The remove operation is not supported.
             *
             * @throws UnsupportedOperationException if the remove operation is called
             */
            @Override
            public void remove()
            {
                throw new UnsupportedOperationException();
            }
        }

    }

}
